import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class project {
    public String findLongestWord(String s, List<String> dictionary) {
        int max=0;
        int index=-1;
        for(int i=0;i<dictionary.size();i++){
            String str=dictionary.get(i);
            int j=0;
            int k=0;
            while (j<s.length()&&k<str.length()){
                char ch1=s.charAt(j);
                char ch2=str.charAt(k);
                if(ch1==ch2){
                    k++;
                }
                j++;
            }
            if(k==str.length()){
                if(k>=max){
                    if(index==-1||k>max){
                        max=k;
                        index=i;
                    }else if(k==max&&compare(dictionary.get(index),dictionary.get(i))){
                        max=k;
                        index=i;
                    }
                }
            }
        }

        return index==-1?"":dictionary.get(index);
    }
    public boolean compare(String s1,String s2){
        for(int i=0;i<s1.length();i++){
            char ch1=s1.charAt(i);
            char ch2=s2.charAt(i);
            if(ch1>ch2){
                return true;
            }else if(ch1<ch2){
                return false;
            }
        }
        return false;
    }




















    public List<String> removeSubfolders(String[] folder) {
        List<String> list=new ArrayList<>();
        Arrays.sort(folder);
        int index=0;
        while (index<folder.length){
            String str=folder[index];
            list.add(str);
            int curIndex=index+1;
            str+="/";
            while (curIndex<folder.length&&folder[curIndex].startsWith(str)){
                curIndex++;
            }
            index=curIndex;
        }
        return list;
    }






















    public long countVowels(String word) {
        long ret=0;
        int len=word.length();
        String str="aeiou";
        for(int i=0;i<len;i++){
            if(str.contains(word.charAt(i)+"")){
                ret+=(long)(i+1)*(len-i);
            }
        }
        return ret;
    }



















    public int[] findDiagonalOrder(int[][] mat) {
        int row=mat.length;
        int col=mat[0].length;
        int[] arr=new int[row*col];
        int x=0;
        int y=0;
        boolean flag=true;
        for(int i=0;i<row*col;i++){
            arr[i]=mat[x][y];
            if(flag){
                x--;
                y++;
                if(x==-1&&y==col){
                    x=1;
                    y=col-1;
                    flag=false;
                }else if(x==-1){
                    x=0;
                    flag=false;
                }else if(y==col){
                    x+=2;
                    y=col-1;
                    flag=false;
                }
            }else{
                x++;
                y--;
                if(y==-1&&x==row){
                    y=1;
                    x=row-1;
                    flag=true;
                }else if(y==-1){
                    y=0;
                    flag=true;
                }else if(x==row){
                    y+=2;
                    x=row-1;
                    flag=true;
                }
            }
        }
        return arr;
    }















    public int[] findRightInterval(int[][] intervals) {
        int len=intervals.length;
        int[] arr=new int[len];
        for(int i=0;i<len;i++){
            int min=Integer.MAX_VALUE;
            int minIndex=-1;
            for(int j=0;j<len;j++){
                if(intervals[j][0]>=intervals[i][1]&&intervals[j][0]<min){
                    min=intervals[j][0];
                    minIndex=j;
                }
            }
            arr[i]=minIndex;
        }
        return arr;
    }
}
